/*
Minimum Window Substring Total Accepted: 38222 Total Submissions: 200958 My Submissions Question Solution
Given a string S and a string T, find the minimum window in S which will contain all the characters in T in complexity O(n).

For example,
S = "ADOBECODEBANC"
T = "ABC"
Minimum window is "BANC".

Note:
If there is no such window in S that covers all characters in T, return the emtpy string "".

If there are multiple such windows, you are guaranteed that there will always be only one unique minimum window in S.
http://www.cnblogs.com/ganganloveu/p/4153041.html;
*/
#include <iostream>
#include "print.h"
#include <vector>
#include <map>
#include <algorithm>

using namespace std;


/***/
//Definition for an interval.
struct Interval {
	int start;
	int end;
	Interval() : start(0), end(0) {}
	Interval(int s, int e) : start(s), end(e) {}
};

class Solution1 {
public:
	string minWindow(string s, string t) {
		if (t.size() == 0)
		{
			return t;
		}
		
		if (s.size() == 0)
		{
			return s;
		}

		int minLength = INT_MAX;

		string res = "";

		if (s.size() < t.size())
		{
			return res;
		}


		map<string, int> dicts;
		map<string, int> cur;
		
		for (int i = 0; i < t.size(); i++)
		{
			dicts[t.substr(i, 1)]++;
		}
		

		for (int i = 0; i <= s.size() - t.size(); i++)
		{
			
			if (dicts.find(s.substr(i, 1)) == dicts.end())
			{
				continue;
			}
			int count = 0;
			cur.clear();
			int j = 0;
			for ( j  = 0;  j < s.size()- i; j++)
			{
				string c = s.substr(i + j, 1);
				if (dicts.find(c) != dicts.end())
				{
					cur[c]++;
					if (cur[c] == dicts[c])
					{
						count++;
					}
				}

				if (count == t.size())
				{
					break;
				}

				if (j -i +1 > minLength)
				{
					break;
				}

			}

			if ((count == t.size())&&(j - i + 1 < minLength))
			{
				res = s.substr(i, j-i+1);
			}
		}

		return res;
	}
};

class Solution {
public:
	string minWindow(string s, string t) {
		if (t.size() == 0)
		{
			return t;
		}

		if (s.size() == 0)
		{
			return s;
		}

		int begin = 0;
		int end = 0;
		int minBegin = 0;
		int minEnd = 0;
		int minSize = INT_MAX;

		vector<int> needFind(128, 0);
		vector<int> found(128, 0);

		for (int i = 0; i < t.size(); i++)
		{
			needFind[t[i]]++;
		}
		found[s[0]]++;
		int count = t.size();
		if (needFind[s[0]] >= found[s[0]])
		{
			count--;
		}
		
	
		while (true)
		{

			if (count == 0)
			{
				while(found[s[begin]] > needFind[s[begin]])
				{
					found[s[begin]]--;
					begin++;
				}
				int size = end - begin + 1;
				if (size < minSize)
				{
					minBegin = begin;
					minEnd = end;
					minSize = size;

				}

			}


			if (end < s.size())
			{
				end++;
				found[s[end]]++;
				if (needFind[s[end]]>=found[s[end]])
				{
					count--;
				}
			}
			else
			{
				break;
			}
		}
		
		if (minSize == INT_MAX)
		{
			return "";
		}

		string res = s.substr(minBegin, minSize);
		return res;
	}
};




struct Foo
{
	Foo(){ }
	Foo(int){ }
	void fun() { }

};

void test()
{
	int a = 1, b = 2, c = 3, d = 4;
	int e = (a < b ? a : c < d ? a : d);
	cout << e << endl;
}

int main()
{
	//int a[] = { 1, 1, 2 };
	string word1 = "ADOBECODEBANC", word2 = "ABC";
	Solution s;

	string res = s.minWindow(word1, word2);



	system("pause");
	return 0;
}